package com.hy.day;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:找出输掉零场或一场比赛的玩家
 *
 * 给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
 * 返回一个长度为 2 的列表 answer ：
 * answer[0] 是所有 没有 输掉任何比赛的玩家列表。
 * answer[1] 是所有恰好输掉 一场 比赛的玩家列表。
 * 两个列表中的值都应该按 递增 顺序返回。
 *
 * 注意：
 * 只考虑那些参与 至少一场 比赛的玩家。
 * 生成的测试用例保证 不存在 两场比赛结果 相同 。
 *
 * User:Mr.Du
 * Date:2024/5/22
 * Time:10:37
 */
public class FindWinners {

    /**
     * 根据比赛结果找到胜利者和失败者列表。
     *
     * @param matches 二维数组，表示比赛结果，每个元素为长度为2的数组，如 [a, b] 表示比赛 a 对战 b，a 胜利。
     *                数组中的数字代表选手的编号。
     * @return 返回一个包含两个列表的列表。第一个列表为胜利者列表，第二个列表为失败者列表。
     */
        public List<List<Integer>> findWinners(int[][] matches) {
            // 初始化一个数组，用于记录每个选手的胜负情况，1 表示胜利，-1 或 -2 表示失败。
            int[] nums = new int[100001];
            // 遍历比赛结果，更新选手的胜负情况。
            for(int[] matche : matches){
                if(nums[matche[0]] == 0) nums[matche[0]] = 1; // 如果选手还未被记录过，则标记为胜利。
                if(nums[matche[1]] >= -2) nums[matche[1]] -= 2; // 选手 b 输掉比赛，标记为失败（-1 或 -2）。
            }
            // 初始化结果列表，分别用于存放胜利者和失败者。
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> l = new ArrayList<>();
            List<Integer> w = new ArrayList<>();
            // 根据记录的胜负情况，将选手归类到胜利者或失败者列表中。
            for(int i = 0;i < nums.length;i++){
                if(nums[i] == 1) w.add(i); // 胜利者。
                if(nums[i] == -1 || nums[i] == -2) l.add(i); // 失败者。
            }
            // 将胜利者和失败者列表添加到结果列表中。
            res.add(w);
            res.add(l);
            return res;

        }

    /**
     * 查找比赛中的胜利者和失败者列表。
     *
     * @param matches 二维数组，表示比赛结果，每个元素为一个数组，包含两个整数表示比赛双方。
     *                假设x胜y，则在w中增加x的计数，在l中增加y的计数。
     * @return 返回一个包含两个列表的列表。第一个列表为只获胜一次的选手列表（胜利者），第二个列表为只失败一次的选手列表（失败者）。
     */
    public List<List<Integer>> findWinners1(int[][] matches) {
        // 胜利者和失败者的计数，使用TreeMap保持有序
        Map<Integer, Integer> w = new TreeMap<>();
        Map<Integer, Integer> l = new TreeMap<>();

        // 遍历比赛记录，更新胜利者和失败者的计数
        for(int[] matche : matches){
            int x = matche[0], y = matche[1];
            w.put(x, w.getOrDefault(x, 0) + 1); // x胜，增加x的胜利计数
            l.put(y, l.getOrDefault(y, 0) + 1); // y负，增加y的失败计数（这里存在错误，应为l.getOrDefault(y, 0) + 1）
        }

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> listL = new ArrayList<>(); // 只失败一次的选手列表
        List<Integer> listW = new ArrayList<>(); // 只胜利一次的选手列表

        // 确定只胜利一次的选手
        for(int k : w.keySet()){
            if(!l.containsKey(k)) listW.add(k);
        }

        // 确定只失败一次的选手
        for(int k : l.keySet()){
            if(l.get(k) == 1) listL.add(k);
        }

        // 收集结果
        res.add(new ArrayList<>(listW));
        res.add(new ArrayList<>(listL));
        return res;

    }
}
